/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head,null);

    }
    public ListNode sortList(ListNode head,ListNode tail){
        if(head==null){
            return head;
        }
        if(head.next==tail){
            head.next=null;
            return head;
        }
        ListNode slow=head,fast=head;
        while(fast!=tail){
            fast=fast.next;
            slow=slow.next;
            if(fast!=tail){
                fast=fast.next;
            }

        }
        ListNode mid=slow;
        ListNode List1=sortList(head,mid);
        ListNode List2=sortList(mid,tail);
        ListNode sorted=merge(List1,List2);
        return sorted;
    }
    public ListNode merge(ListNode head1,ListNode head2){
        ListNode Head=new ListNode(0);
        ListNode temp=Head,temp1=head1,temp2=head2;
        while(temp1!=null&&temp2!=null){
            if(temp1.val<=temp2.val){
                temp.next=temp1;
                temp1=temp1.next;
            }else{
                temp.next=temp2;
                temp2=temp2.next;
            }
            temp=temp.next;
        }
        if(temp1!=null){
            temp.next=temp1;

        }else if(temp2!=null){
            temp.next=temp2;
        }
        return Head.next;

    }
}

